package gold.digger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC140 {

    Map<String, List<String>> memo = new HashMap<>();

    public List<String> wordBreak(String str, List<String> wordDict) {
        if (memo.containsKey(str)) {
            return memo.get(str);
        }

        List<String> res = new ArrayList<>();
        if (null == wordDict || null == str || str.length() <= 0) {
            return res;
        }


        for (String word : wordDict) {
            if (str.startsWith(word)) {
                List<String> subRes = wordBreak(str.substring(word.length()), wordDict);
                for (String subSentence : subRes) {
                    res.add(word + " " + subSentence);
                }
            }

            if (str.equals(word)) {
                res.add(word);
            }
        }

        memo.put(str, res);
        return res;
    }

    public List<String> wordBreakT(String str, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        if (null == wordDict || null == str || str.length() <= 0) {
            return res;
        }

        HashSet wordDictSet = new HashSet<String>(wordDict);
        if (wordDictSet.contains(str)) {
            return new ArrayList<>(Arrays.asList(str));
        }

        List<List<String>> dp = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            List<String> curRes = new ArrayList<>();
            for (int j = -1; j < i; j++) {
                List<String> subResJ = j == -1 ? new ArrayList<>() : dp.get(j);
                String partStr = str.substring(j + 1, i + 1);
                if (!wordDictSet.contains(partStr)) {
                    continue;
                }

                if (subResJ.size() <= 0 && j == -1) {
                    curRes.add(partStr);
                } else {
                    for (String sentenceJ : subResJ) {
                        curRes.add(sentenceJ + " " + partStr);
                    }
                }
            }

            dp.add(curRes);
        }

        List<String> desRes = dp.get(str.length() - 1);
        String desResStr = desRes.size() >= 1 ? desRes.get(0) : "";
        return desResStr.length() >= str.length() ? desRes : new ArrayList<>();
    }


    public static void main(String[] args) {
        LC140 an = new LC140();
        String s = "aaa";
        List<String> wordDict = Arrays.asList("aa", "a");
        System.out.println(an.wordBreak(s, wordDict));
    }
}
